package zy.boring.order.impl;

import zy.boring.order.QuickOrder;

public class QuickOrderImpl implements QuickOrder {

	@Override
	public int[] quickOrder(int[]data, int low, int high) {
		//定义局部变量i,j,初始i,j是递归的首位两个元素的索引
		int i = low;
		int j = high;
		//一开始老不能结束递归，加了这句
		if(low<high){
			//确定数组第一个元素为目标元素
			int keyInt = data[i];
			//确保i始终小于j
			while(i<j){
				//首先通过第一个元素（keyInt）跟从末尾开始的元素逐一比较,找到比keyInt小的元素
				while(i<j && keyInt<data[j]){
					j--;
				}
				//把data[i]交换
				if(i<j){
					data[i] = data[j];
					//焦点向右移
					i++;
				}
				//通过keyInt从头开始的元素逐一比较,找到比keyInt大的元素
				//这里开始的时候没有加i<j这句，导致了错误，要时刻保持i<j
				while(i<j && keyInt>data[i]){
					i++;
				}
				//data[j]交换
				if(i<j){
					data[j] = data[i];
					//焦点向左移
					j--;
				}
			}
			data[i] = keyInt;
			//调用递归，分别把左半边跟又半边进行排序
				quickOrder(data,low,i);
				quickOrder(data,i+1,high);
		}
		return data;
	}

}
